# 给定两个用链表表示的整数，每个节点包含一个数位。 
# 
#  这些数位是反向存放的，也就是个位排在链表首部。 
# 
#  编写函数对这两个整数求和，并用链表形式返回结果。 
# 
#  
# 
#  示例： 
# 
#  输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
# 输出：2 -> 1 -> 9，即912
#  
# 
#  进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢? 
# 
#  示例： 
# 
#  输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
# 输出：9 -> 1 -> 2，即912
#  
# 
#  Related Topics 递归 链表 数学 👍 199 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, Link, LinkedListTool


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
"""
如果是正向存放，则可以考虑把数字翻转后再采用如下方法
"""
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        curr = dummy
        carry = 0
        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            total = x + y + carry
            carry = total // 10
            val = total % 10

            curr.next = ListNode(val=val)

            # 移动指针
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next


# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().addTwoNumbers(LinkedListTool([9, 9, 9, 9, 9, 9, 9]), LinkedListTool([9, 9, 9, 9])))
